Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
方法1:迭代法
首先需要将当前节点cur的下一节点next暂存起来,然后将当前节点cur反转指向上一节点pre。再让当前节点cur变为pre,下一节点next变为cur,循环反转。
1 | /** |
方法2:递归法
首先找到最后一个节点,返回值用p保存并返回给上一层调用,然后从最后一个节点的上一个节点开始反转链表,递归调用。最后返回原来的最后一个节点。1
2
3
4
5
6
7
8
9class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}